use rand::Rng;

fn sieve_of_eratosthenes(limit: u128) -> Vec<u128> {
    let mut sieve = vec![true; (limit + 1) as usize];
    sieve[0] = false;
    sieve[1] = false;

    for i in 2..((limit as f64).sqrt() as u128 + 1) {
        if sieve[i as usize] {
            for j in (i * i..=limit).step_by(i as usize) {
                sieve[j as usize] = false;
            }
        }
    }

    sieve.into_iter().enumerate()
        .filter_map(|(i, is_prime)| if is_prime { Some(i as u128) } else { None })
        .collect()
}

fn mod_exp(base: u128, exp: u128, modulus: u128) -> u128 {
    let mut result = 1;
    let mut base = base % modulus;
    let mut exp = exp;

    while exp > 0 {
        if exp % 2 == 1 {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exp /= 2;
    }
    result
}

fn miller_rabin(n: u128, k: u64) -> bool {
    if n <= 1 {
        return false;
    }
    if n == 2 || n == 3 {
        return true; 
    }
    if n % 2 == 0 {
        return false; 
    }

    let mut d = n - 1;
    let mut s = 0;
    while d % 2 == 0 {
        d /= 2;
        s += 1;
    }

    for _ in 0..k {
        let a = rand::thread_rng().gen_range(2..n - 1);
        let mut x = mod_exp(a, d, n);

        if x == 1 || x == n - 1 {
            continue;
        }

        let mut is_composite = true;
        for _ in 0..s - 1 {
            x = mod_exp(x, 2, n);
            if x == n - 1 {
                is_composite = false;
                break;
            }
        }

        if is_composite {
            return false;
        }
    }

    true
}

pub fn find_max_prime_factor(mut number: u128) -> u128 {
    let sieve_limit = 10_000_000u128; 

    let primes = sieve_of_eratosthenes(sieve_limit);

    let mut max_factor = 1u128;

    for p in &primes {
        while number % p == 0 {
            max_factor = *p;  
            number /= p;  
        }
    }

    if number > 1 {
        if miller_rabin(number, 10) {
            max_factor = number;
        }
    }

    max_factor
}
